package com.sourcetrip.algorithm.sort.heap;

import com.sourcetrip.algorithm.abs.AbstractSort;

/**
 * @author: ZhouBert
 * @date: 2020/12/28
 * @description: 十大排序算法之 third 堆排序
 * 分析：
 * 从选择排序中可以发现，有个取最大值的操作，而二叉堆恰好是用数组实现的，所以可以用二叉堆来替代选择排序的取最大值操作。
 * 所以，可以把堆排序看作是【选择排序的算法改进版本！】
 */
public class HeapSortV0 extends AbstractSort {

	/**
	 * 将找出元素中最大的值改为从二叉堆中获取堆顶元素。
	 * 虽然上次自己实现堆的时候独立完成了单个元素的上滤和下滤，但是对于原地建堆还没有实现过。
	 *
	 * @param arr
	 * @return
	 */
	@Override
	protected int[] sortArr(int[] arr) {
		//1.原地建堆（heapify）
		//原地建堆有两种方法：
		//-1-shiftUp	上滤 O(nlogn)
		//-2-shiftDown	下滤 O(n)
		heapify(arr);

		//2.
		int size = arr.length;
		for (int end = arr.length - 1; end >= 0; end--) {
			//1.交换 end 与 0 的值
			swap(arr, 0, end);
			//2.size--
			//3.sift down 0
			siftDown(0, arr, --size);
		}

		//
		return arr;
	}

	/**
	 * 将数组原地建堆
	 *
	 * @param arr
	 */
	private void heapify(int[] arr) {
		for (int i = arr.length - 1; i >= 0; i--) {
			siftDown(i, arr, arr.length);
		}
	}

	/**
	 * 将index 处的元素下滤
	 *
	 * @param index
	 * @param arr
	 */
	private void siftDown(int index, int[] arr, int size) {
		int rightIndex = getRightChildIndex(index);
		while (rightIndex < size) {
			//在这里保持稳定，左边说明靠前，如果相等，依然是取左边的，那么即使发生了交换，左右节点在数组中的前后位置保持不变！
			int biggerIndex = arr[rightIndex - 1] >= arr[rightIndex] ? rightIndex - 1 : rightIndex;
			if (arr[biggerIndex] > arr[index]) {
				swap(arr, biggerIndex, index);

				index = biggerIndex;
				rightIndex = getRightChildIndex(index);
			} else {
				return;
			}
		}
		//此时如果还有左节点
		if (rightIndex == size) {
			if (arr[rightIndex - 1] > arr[index]) {
				swap(arr, rightIndex - 1, index);
			}
		}
	}


	private int getParentIndex(int index) {
		return (index - 1) >> 1;
	}

	private int getLeftChildIndex(int index) {
		return (index << 1) + 1;
	}

	private int getRightChildIndex(int index) {
		return (index << 1) + 2;
	}

}
